package com.leetcode.algorithm.y18.m06;

import java.util.Arrays;

/**
 * leetcode-cn.com
 * (done)674. 最长连续递增序列
 * (done)665. 非递减数列
 * (done)661. 图片平滑器
 * (done)643. 子数组最大平均数 I
 * (done)628. 三个数的最大乘积
 * @author: jie.deng
 * @time: 2018年6月8日 上午10:11:20
 */
public class MySolution0608 {
	
	/**
	 * 674. 最长连续递增序列
	 * 给定一个未经排序的整数数组，找到最长且连续的的递增序列。
	 * 
	 * 示例 1:
	 * 
	 * 输入: [1,3,5,4,7]
	 * 输出: 3
	 * 解释: 最长连续递增序列是 [1,3,5], 长度为3。
	 * 尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为5和7在原数组里被4隔开。 
	 * 示例 2:
	 * 
	 * 输入: [2,2,2,2,2]
	 * 输出: 1
	 * 解释: 最长连续递增序列是 [2], 长度为1。
	 * 注意：数组长度不会超过10000。
	 * @param nums
	 * @return
	 */
	public int findLengthOfLCIS(int[] nums) {
		int len = nums.length;
		if (len == 0) {
			return 0;
		}
		int beginIdx = 0;
		int count = 1;
		int i = 1;
		for (; i < len; i++) {
			if (nums[i] <= nums[i - 1]) {
				count = Math.max(count, i - beginIdx);
				beginIdx = i;
			}
		}
		count = Math.max(count, i - beginIdx);
		return count;
	}
    
	/**
	 * 665. 非递减数列
	 * 给定一个长度为 n 的整数数组，你的任务是判断在最多改变 1 个元素的情况下，该数组能否变成一个非递减数列。
	 * 
	 * 我们是这样定义一个非递减数列的： 对于数组中所有的 i (1 <= i < n)，满足 array[i] <= array[i + 1]。
	 * 
	 * 示例 1:
	 * 
	 * 输入: [4,2,3]
	 * 输出: True
	 * 解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。
	 * 示例 2:
	 * 
	 * 输入: [4,2,1]
	 * 输出: False
	 * 解释: 你不能在只改变一个元素的情况下将其变为非递减数列。
	 * 说明:  n 的范围为 [1, 10,000]。
	 * @param nums
	 * @return
	 */
	public boolean checkPossibility(int[] nums) {
		int len = nums.length;
		for (int i = 0; i < len - 1; i++) {
			if (nums[i] > nums[i + 1]) {
				// 考虑两种情况，把nums[i]替换掉，或者把nums[i + 1]替换掉
				int j = 0;
				if (i == 0 || nums[i - 1] <= nums[i + 1]) {
					j = i + 1;// 把nums[i]替换掉
				} else if (i == len - 2 || nums[i] <= nums[i + 2]) {
					j = i + 2;// 把nums[i + 1]替换掉
				} else {
					return false;
				}
				for (; j < len - 1; j++) {
					if (nums[j] > nums[j + 1]) {
						return false;
					}
				}
				break;
			}
		}
		return true;
	}
    
    
    /**
     * 661. 图片平滑器
	 * 包含整数的二维矩阵 M 表示一个图片的灰度。你需要设计一个平滑器来让每一个单元的灰度成为平均灰度 (向下舍入) ，平均灰度的计算是周围的8个单元和它本身的值求平均，如果周围的单元格不足八个，则尽可能多的利用它们。
	 * 
	 * 示例 1:
	 * 
	 * 输入:
	 * [[1,1,1],
	 *  [1,0,1],
	 *  [1,1,1]]
	 * 输出:
	 * [[0, 0, 0],
	 *  [0, 0, 0],
	 *  [0, 0, 0]]
	 * 解释:
	 * 对于点 (0,0), (0,2), (2,0), (2,2): 平均(3/4) = 平均(0.75) = 0
	 * 对于点 (0,1), (1,0), (1,2), (2,1): 平均(5/6) = 平均(0.83333333) = 0
	 * 对于点 (1,1): 平均(8/9) = 平均(0.88888889) = 0
	 * 注意:
	 * 
	 * 给定矩阵中的整数范围为 [0, 255]。
	 * 矩阵的长和宽的范围均为 [1, 150]。
     * @param M
     * @return
     */
	public int[][] imageSmoother(int[][] M) {
		int row = M.length;
		int col = M[0].length;
		int[][] ret = new int[row][col];
		for (int j = 0; j < col; j++) {
			int cnt = 1;
			ret[0][j] = M[0][j];
			if (row > 1) {
				ret[0][j] += M[1][j];
				cnt += 1;
			}
			if (j != 0) {
				ret[0][j] += M[0][j - 1];
				cnt += 1;
				if (row > 1) {
					ret[0][j] += M[1][j - 1];
					cnt += 1;
				}
			}
			if (col > 1 && j != col - 1) {
				ret[0][j] += M[0][j + 1];
				cnt += 1;
				if (row > 1) {
					ret[0][j] += M[1][j + 1];
					cnt += 1;
				}
			}
			ret[0][j] = (int) Math.floor(ret[0][j] / cnt);

			if (row > 1) {
				ret[row - 1][j] += M[row - 1][j];
				ret[row - 1][j] += M[row - 2][j];
				cnt = 2;
				if (j != 0) {
					ret[row - 1][j] += M[row - 1][j - 1];
					ret[row - 1][j] += M[row - 2][j - 1];
					cnt += 2;
				}
				if (col > 1 && j != col - 1) {
					ret[row - 1][j] += M[row - 1][j + 1];
					ret[row - 1][j] += M[row - 2][j + 1];
					cnt += 2;
				}
				ret[row - 1][j] = (int) Math.floor(ret[row - 1][j] / cnt);
			}
		}
		for (int i = 1; i < row - 1; i++) {
			ret[i][0] += M[i][0];
			ret[i][0] += M[i - 1][0];
			ret[i][0] += M[i + 1][0];
			int cnt = 3;
			if (col > 1) {
				ret[i][0] += M[i][1];
				ret[i][0] += M[i - 1][1];
				ret[i][0] += M[i + 1][1];
				cnt += 3;
			}
			ret[i][0] = (int) Math.floor(ret[i][0] / cnt);
			if (col > 1) {
				ret[i][col - 1] += M[i][col - 1];
				ret[i][col - 1] += M[i - 1][col - 1];
				ret[i][col - 1] += M[i + 1][col - 1];
				ret[i][col - 1] += M[i][col - 2];
				ret[i][col - 1] += M[i - 1][col - 2];
				ret[i][col - 1] += M[i + 1][col - 2];
				ret[i][col - 1] = (int) Math.floor(ret[i][col - 1] / 6);
			}
		}

		for (int i = 1; i < row - 1; i++) {
			for (int j = 1; j < col - 1; j++) {
				ret[i][j] += M[i][j];
				ret[i][j] += M[i - 1][j - 1];
				ret[i][j] += M[i - 1][j];
				ret[i][j] += M[i - 1][j + 1];
				ret[i][j] += M[i][j - 1];
				ret[i][j] += M[i][j + 1];
				ret[i][j] += M[i + 1][j - 1];
				ret[i][j] += M[i + 1][j];
				ret[i][j] += M[i + 1][j + 1];
				ret[i][j] = (int) Math.floor(ret[i][j] / 9);
			}
		}

		return ret;
	}
    
    /**
     * 643. 子数组最大平均数 I
	 * 给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。
	 * 
	 * 示例 1:
	 * 
	 * 输入: [1,12,-5,-6,50,3], k = 4
	 * 输出: 12.75
	 * 解释: 最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
	 *  
	 * 
	 * 注意:
	 * 
	 * 1 <= k <= n <= 30,000。
	 * 所给数据范围 [-10,000，10,000]。
     * @param nums
     * @param k
     * @return
     */
	public double findMaxAverage(int[] nums, int k) {
		int len = nums.length;
		int sum = 0;
		for (int i = 0; i < k; i++) {
			sum += nums[i];
		}
		int maxSum = sum;
		for (int i = 1; i <= len - k; i++) {
			sum = sum + nums[i + k - 1] - nums[i - 1];
			maxSum = Math.max(maxSum, sum);
		}
		return maxSum / (double) k;
	}

	/**
	 * 628. 三个数的最大乘积
	 * 给定一个整型数组，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
	 * 
	 * 示例 1:
	 * 
	 * 输入: [1,2,3]
	 * 输出: 6
	 * 示例 2:
	 * 
	 * 输入: [1,2,3,4]
	 * 输出: 24
	 * 注意:
	 * 
	 * 给定的整型数组长度范围是[3,104]，数组中所有的元素范围是[-1000, 1000]。
	 * 输入的数组中任意三个数的乘积不会超出32位有符号整数的范围。
	 * @param nums
	 * @return
	 */
	public int maximumProduct(int[] nums) {
		Arrays.sort(nums);
		int len = nums.length;
		if (nums[len - 1] == 0) {
			return 0;
		} else if (nums[len - 1] > 0) {
			return nums[len - 1] * Math.max(nums[len - 2] * nums[len - 3], nums[0] * nums[1]);
		} else {
			return nums[len - 1] * nums[len - 2] * nums[len - 3];
		}
	}

	public int maximumProductSolution(int[] nums) {
		int max1 = Integer.MIN_VALUE; // 最大的
		int max2 = Integer.MIN_VALUE;
		int max3 = Integer.MIN_VALUE;
		int min1 = Integer.MAX_VALUE; // 最小的
		int min2 = Integer.MAX_VALUE;
		int len = nums.length;
		for (int i = 0; i < len; i++) {
			if (nums[i] > max3) {
				if (nums[i] >= max2) {
					if (nums[i] >= max1) {
						max3 = max2;
						max2 = max1;
						max1 = nums[i];
					} else {
						max3 = max2;
						max2 = nums[i];
					}
				} else {
					max3 = nums[i];
				}
			}
			if (nums[i] < min2) {
				if (nums[i] <= min1) {
					min2 = min1;
					min1 = nums[i];
				} else {
					min2 = nums[i];
				}
			}
		}
		return max1 * Math.max(max2 * max3, min1 * min2);
	}
    
}
